package chapter3_v4;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @author mazouri
 * @create 2021-10-31 22:27
 */
public class BFSPaths {
    private boolean[] marked;
    private int[] edgeTo;
    private int s; // 起点

    public BFSPaths(Graph G, int s) {
        this.marked = new boolean[G.V()];
        this.edgeTo = new int[G.V()];
        this.s = s;
        bfs(G, s);
    }

    private void bfs(Graph G, int s) {
        Queue<Integer> queue = new LinkedList<>();
        marked[s] = true;
        queue.offer(s);
        while (!queue.isEmpty()) {
            Integer v = queue.poll();
            for (Integer w : G.adj(v)) {
                if (!marked[w]) {
                    edgeTo[w] = v;
                    marked[w] = true;
                    queue.offer(w);
                }
            }
        }
    }

    public boolean hasPathTo(int v) {
        return marked[v];
    }

    public Stack<Integer> pathTo(int v) {
        if (!hasPathTo(v)) return null;
        Stack<Integer> path = new Stack<>();
        int x;
        for (x = v; x != s; x = edgeTo[x])
            path.push(x);
        path.push(x);
        return path;
    }

    public static void main(String[] args) {
        Graph G = new Graph(6);
        G.addEdge(0, 5);
        G.addEdge(0, 1);
        G.addEdge(0, 2);
        G.addEdge(2, 1);
        G.addEdge(5, 3);
        G.addEdge(3, 4);
        G.addEdge(2, 3);
        G.addEdge(2, 4);
        int s = 0;
        BFSPaths bfsPaths = new BFSPaths(G, s);
        for (int i = 0; i < G.V(); i++) {
            System.out.print(s + " to " + i + ": ");
            Stack<Integer> stack = bfsPaths.pathTo(i);

            int size = stack.size();
            for (int x = 0; x < size; x++) {
                if (x == s) System.out.print(stack.pop());
                else System.out.print("-" + stack.pop());
            }

            System.out.println();
        }
    }
}
